Time and space switching fabrics have been used for many years in a variety of switching and multiplexing devices including SONET cross-connects, SONET add-drop multiplexers, SONET terminal multiplexers, and digital signal-level 0 (DS0) switches. Such fabrics use connection scheduling algorithms to map customers' connection requirements into switch settings for the fabrics' control registers. The basic scheduling problem is to find the switch settings required to properly route a set of connections.
The so-called “Slepian-Duguid” prior art algorithm has been used to schedule connections in rearrangeably non-blocking switches. This algorithm makes use of “Paull's matrix”, which is formed by labelling the switch's input ports as the matrix rows; and by labelling the switch's output ports as the matrix columns. Each matrix entry (i, j) is either blank, indicating no connection between switch input port i and output port j; or, contains an identifier for the intermediate switch on which the connection of input port i to output port j is allocated. The basic Slepian-Duguid algorithm is depicted in flowchart form in FIG. 1. Although the algorithm is shown with a failure terminal point, the failure only indicates that either the input port or output port has been over-allocated. The Slepian-Duguid algorithm always succeeds on loads of up to 100% capacity.
A simple 3 input to 3 output switch is shown in FIG. 2. The FIG. 2 switch has two intermediate 3×3 switches labelled “A” and “B”. Each intermediate switch can accept one unit of data per cycle on each of its inputs and switch that unit on one of its outputs. Two data units may not utilize the same output at the same time. Therefore, inputs must be scheduled to prevent contention for the outputs of intermediate switches A and B. In practice, “A” and “B” may represent the same actual switch at different times: “A” could represent the switch during one cycle and “B” may represent the same switch during the following cycle. Such a switch could be used to switch 2-unit multiplexed traffic on its input ports. Alternatively, “A” and “B” could represent two separate switches which perform parallel switching functions, with data arriving at the input ports in parallel, two units wide.
The FIG. 2 switch is a simplified example of a “rearrangeably non-blocking” switch. Switch input port to output port “mappings” are represented as (n,m) where n designates one of the switch input ports, and m designates one of the A or B switch output ports. Thus, (1,3) represents a mapping of switch input port 1 to switch output port 3. A switch is “non-blocking” if every load of 100% or less can be mapped successfully from the switch's input ports to the switch's output ports. A switch is “rearrangeably non-blocking” if a new mapping may require the rearrangement of persistent connections. For the FIG. 2 switches A and B, a mapping is not over-allocated (100% load or less) if each input and output appears no more than twice in the mapping. For example, the mapping {(1, 2), (1,3), (2, 2), (3, 2)} is over-allocated because output port 2 appears three times in the mapping. Each output port of FIG. 2 switches A and B can accept at most two inputs and each input port of FIG. 2 switches A and B can contribute at most 2 inputs in a mapping.
Progress of the Slepian-Duguid algorithm in scheduling the mapping of connections {(1, 3), (2, 1), (2, 3), (3, 2), (3, 1)} is shown in FIGS. 3, 4, 5 and 6. The Paull's matrix of FIG. 3 depicts the initial state in which no connections have been scheduled. FIG. 4 depicts addition of the first connection, (1, 3), which is arbitrarily assigned to switch A as indicated in FIG. 1, block 12. FIG. 5 depicts addition of the next three connections (2, 1), (2, 3), (3, 2) with the second connection (2,1) having been assigned to switch A and connections (2, 3), (3, 2) assigned to switch B. FIG. 6 shows how the Slepian-Duguid algorithm rearranges the previous scheduling (i.e. that depicted in FIG. 5) to satisfy a request for an additional connection (3,1).
In FIG. 6, the underlined letters denote the previous (i.e. FIG. 5) switch assignments and the non-underlined letters denote the assignments required to permit addition of the newly requested connection (3,1). As indicated in FIG. 1, block 10 the algorithm tests the Paull's matrix representation of the FIG. 2 switch fabric to determine whether switch A is not yet mentioned in row i=3 and column j=1 of the matrix. As seen in FIG. 5, switch A is not mentioned in row 3; but, it is mentioned in column 1, in respect of the previously scheduled connection (2,1). The FIG. 1, block 10 test result is accordingly “no” and processing continues with block 14.
The algorithm then tests (block 14) the Paull's matrix representation of the FIG. 2 switch fabric to determine whether there is a switch A that does not occur in row i=3 and a switch B that does not occur in column j=1. In the case of the FIG. 5 matrix the answer is “yes” (i.e. there is no ‘A’ in row 3, and no ‘B’ in column 1 of the FIG. 5 matrix). The FIG. 1, block 14 test result is accordingly “yes”, and processing continues with block 20. If the FIG. 1, block 14 test result had been “no” this would signify that the FIG. 2 switch fabric has insufficient resources to satisfy the (3,1) connection scheduling request and the algorithm would therefore terminate in failure mode as indicated in FIG. 1, blocks 16, 18.
The algorithm then schedules connection (3,1) for switch A as indicated in FIG. 1, block 20 and as illustrated in FIG. 6. It is then necessary to reschedule or “flip” connection (2,1) from switch A to switch B to prevent over-allocation of switch A's connection to output 1. This is accomplished as shown in FIG. 1, blocks 22-34. First, as indicated in block 22, the existing switch A entry (i.e. that for connection (2,1)) in column 1 is flipped to switch B (i.e. i′=2). A test (block 24) is then made to determine whether the Paull's matrix representation of the FIG. 2 switch fabric includes another entry for switch B in row i′=2. The answer in this case is “yes”, namely the previously scheduled connection (2,3). This necessitates flipping connection (2,3) from switch B to switch A to prevent over-allocation of the input connection to switch B. More particularly, if the block 24 test result is “yes”, processing continues with block 26 such that the existing switch B entry (2,3) is flipped to switch A (i.e. i′=2 and j′=3). The algorithm then tests (block 30) the Paull's matrix representation of the FIG. 2 switch fabric to determine whether there is another entry for switch A in column j′=3. If the answer is “no” the algorithm terminates successfully as indicated at block 34, but the answer in this case is “yes”, namely the previously scheduled connection (1,3). This necessitates flipping connection (1,3) from switch A to switch B to prevent over-allocation of the input connection to switch A. More particularly, if the block 30 test result is “yes”, processing continues with block 32 which assigns i=i′=2 and j=j′=3. Accordingly, when processing then continues with block 22, the existing switch A entry in row 1, column 3 is flipped to switch B (i.e. i′=1). The block 24 test is then again made to determine whether the Paull's matrix representation of the FIG. 2 switch fabric includes another entry for switch B in row 1. The answer in this case is “no”, and the algorithm terminates successfully as indicated at block 28.
Any entry in the matrix may designate more than one switch to indicate a repeated connection. For example, if “A” and “B” appeared together in the matrix row-column entry corresponding to connection (3,1) this would indicate that both units of data contributed by input 3 are to be output on port 1.
A standard technique for optimizing the Slepian-Duguid algorithm is to find the fewest number of entries that need to be “flipped” and work in that direction. For example, if instead of assigning connection (3,1) to switch A as discussed above, connection (3,1) were instead assigned to switch B, then it would only have been necessary to flip connection (3,2) from switch B to switch A rather than making the three previously described flips. In any case, the number of rearrangements (flips) required to add any connection is limited by I+O where “I” is the number of inputs and “O” the number of outputs. In practice, if the shortest number of entries needing to be flipped is always chosen, then the number of rearrangements is reduced to min(I,O)−1.
Implementation of Paull's matrix as a two dimensional matrix of input ports to output ports is computationally expensive and unnecessary. Paull's matrix is a sparse matrix, in that most of the matrix row-column entries are blank. A significantly reduced representation of Paull's matrix can be constructed. Specifically, instead of the 2-dimensional matrices shown in FIGS. 3-6, one may use two one dimensional arrays as shown in FIGS. 7-8 to achieve a reduction in size due to the fact that an intermediate switch can only occur once per row and once per column.
In the first array (i.e. the left hand arrays of FIGS. 7-8), there are as many entries as the number of inputs, with each such entry consisting of a sub-array having as many entries as the number of intermediate switches. In the sub-array, each entry is set to null if the corresponding intermediate switch is not used by the corresponding input. If an intermediate switch is used by an input, then the entry for that switch designates the output to which that switch directs the input. Similarly, the second array (i.e. the right hand arrays of FIGS. 7-8), has as many entries as the number of outputs, with each such entry consisting of a sub-array having as many entries as the number of intermediate switches. In this sub-array, each entry is set to null if the corresponding intermediate switch is not used to deliver data to the corresponding output. If an intermediate switch delivers data to a particular output, then the entry for that switch designates the input from which that switch directs the data.
More particularly, FIG. 7 is a compact representation of the Paull's matrix depicted in FIG. 5. The first (i.e. left hand) array has three entries (i.e. rows): one for each of the three inputs utilized by connections (1, 3), (2, 1), (2, 3), (3, 2). Each one of these three entries is a sub-array having two entries (i.e. columns): one for each of the two intermediate switches A and B. The second (i.e. right hand) array has three entries (i.e. rows): one for each of the three outputs utilized by connections (1, 3), (2, 1), (2, 3), (3, 2). Each one of these three entries is a sub-array having two entries (i.e. columns): one for each of the two intermediate switches A and B. FIG. 8 is a compact representation of the Paull's matrix depicted in FIG. 6 with the addition of connection (3,1) following the same path as described above. In FIG. 8, entries of the form x/y reflect the fact that prior to the addition of (3,1), x was the previous entry, with y being the new entry after addition of (3, 1). The compact representation improves the efficiency with which unused intermediate switches can be located.
The present invention simplifies solution of the connection scheduling problem by decoupling time cycles (or switch paths) into a plurality of independent “waves”. Each wave clearly indicates the manner in which inputs and outputs utilized by that wave's time cycle (or switch path) are affected as switch labels are changed during different attempts to solve the connection scheduling problem. By contrast, it is difficult, using Paull's matrix representations consisting of only two input/output arrays, to predict what portions of the input or output arrays may be affected by changing switch labels during different attempts to solve the connection scheduling problem.